'''
算法思想
归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用，
归并排序将两个已经有序的子序列合并成一个有序的序列。
算法流程
主要两步(拆分，合并)
步骤１：进行序列拆分，一直拆分到只有一个元素；
步骤２：拆分完成后，开始递归合并。
思路：假设我们有一个没有排好序的序列，那么我们首先使用拆分的方法将这个序列分割成一个个已经排好序的子序列（直到剩下一个元素）。
然后再利用归并方法将一个个有序的子序列合并成排好序的序列。
'''
'''
时间复杂度：O(N*logN) -->最好、最坏、评价
空间复杂度：O(N)
'''

def merge_sort(lst):
    def merge(left,right):
        i = 0
        j = 0
        result = []
        while i < len(left) and j < len(right):
            if left[i] <right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        return result + left[i:] + right[j:]
    n = len(lst)
    if n <= 1:
        return lst
    mid = n // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return merge(left,right)

# print(merge_sort([5,4,3,2,1]))


# nums = [5,4,3,2,1]
nums = [5,5,2,3,4,1,1,3]
print(merge_sort(nums))
